<!DOCTYPE html>
<html lang="zh-CN">
<head>
  <meta charset="UTF-8">
<meta name="viewport" content="width=device-width">
<meta name="theme-color" content="#222"><meta name="generator" content="Hexo 6.3.0">

  <link rel="apple-touch-icon" sizes="180x180" href="/images/apple-touch-icon-next.png">
  <link rel="icon" type="image/png" sizes="32x32" href="/favicon.ico">
  <link rel="icon" type="image/png" sizes="16x16" href="/favicon-16x16.ico">
  <link rel="mask-icon" href="/images/logo.svg" color="#222">

<link rel="stylesheet" href="/css/main.css">



<link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/@fortawesome/fontawesome-free@6.7.2/css/all.min.css" integrity="sha256-dABdfBfUoC8vJUBOwGVdm8L9qlMWaHTIfXt+7GnZCIo=" crossorigin="anonymous">
  <link rel="stylesheet" href="https://fastly.jsdelivr.net/npm/animate.css@3.1.1/animate.min.css" integrity="sha256-PR7ttpcvz8qrF57fur/yAx1qXMFJeJFiA6pSzWi0OIE=" crossorigin="anonymous">

<script class="next-config" data-name="main" type="application/json">{"hostname":"blog.csgrandeur.cn","root":"/","images":"/images","scheme":"Gemini","darkmode":false,"version":"8.22.0","exturl":false,"sidebar":{"position":"left","width_expanded":320,"width_dual_column":240,"display":"post","padding":18,"offset":12},"hljswrap":true,"copycode":{"enable":true,"style":"default"},"fold":{"enable":false,"height":500},"bookmark":{"enable":false,"color":"#222","save":"auto"},"mediumzoom":false,"lazyload":false,"pangu":false,"comments":{"style":"tabs","active":null,"storage":true,"lazyload":false,"nav":null},"stickytabs":false,"motion":{"enable":true,"async":false,"duration":200,"transition":{"menu_item":"fadeInDown","post_block":"fadeIn","post_header":"fadeInDown","post_body":"fadeInDown","coll_header":"fadeInLeft","sidebar":"fadeInUp"}},"prism":false,"i18n":{"placeholder":"搜索...","empty":"没有找到任何搜索结果：${query}","hits_time":"找到 ${hits} 个搜索结果（用时 ${time} 毫秒）","hits":"找到 ${hits} 个搜索结果"},"path":"/search.xml","localsearch":{"enable":true,"top_n_per_article":1,"unescape":false,"preload":false,"trigger":"auto"}}</script><script src="/js/config.js"></script>

    <meta name="description" content="字符串算法 KMP、AC自动机、字符串哈希、最小表示法。">
<meta property="og:type" content="article">
<meta property="og:title" content="34.字符串算法">
<meta property="og:url" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/index.html">
<meta property="og:site_name" content="CSGrandeur&#39;s Thinking">
<meta property="og:description" content="字符串算法 KMP、AC自动机、字符串哈希、最小表示法。">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E6%9A%B4%E5%8A%9B.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E6%80%9D%E8%80%83%E6%9A%B4%E5%8A%9B%E6%94%B9%E8%BF%9B.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E5%9F%BA%E6%9C%AC%E6%80%9D%E6%83%B3.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_next%E6%95%B0%E7%BB%84.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_next%E8%AE%A1%E7%AE%97%E5%8A%A8%E6%80%81%E6%BC%94%E7%A4%BA.gif">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E5%8C%B9%E9%85%8D%E6%BC%94%E7%A4%BA.gif">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/ac%E8%87%AA%E5%8A%A8%E6%9C%BA_trie.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/ac%E8%87%AA%E5%8A%A8%E6%9C%BA.svg">
<meta property="og:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/%E6%9C%80%E5%B0%8F%E8%A1%A8%E7%A4%BA_ijn.svg">
<meta property="article:published_time" content="2025-06-04T07:59:11.000Z">
<meta property="article:modified_time" content="2025-06-12T09:25:17.384Z">
<meta property="article:author" content="CSGrandeur">
<meta property="article:tag" content="ACM">
<meta property="article:tag" content="Algorithm">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E6%9A%B4%E5%8A%9B.svg">


<link rel="canonical" href="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/">


<script class="next-config" data-name="page" type="application/json">{"sidebar":"","isHome":false,"isPost":true,"lang":"zh-CN","comments":true,"permalink":"http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/","path":"2025-06-04-34-字符串算法/","title":"34.字符串算法"}</script>

<script class="next-config" data-name="calendar" type="application/json">""</script>
<title>34.字符串算法 | CSGrandeur's Thinking</title>
  

  <script src="/js/third-party/analytics/baidu-analytics.js"></script>
  <script async src="https://hm.baidu.com/hm.js?7958adf931092425a489778560129144"></script>







  <noscript>
    <link rel="stylesheet" href="/css/noscript.css">
  </noscript>
</head>

<body itemscope itemtype="http://schema.org/WebPage" class="use-motion">
  <div class="headband"></div>

  <main class="main">
    <div class="column">
      <header class="header" itemscope itemtype="http://schema.org/WPHeader"><div class="site-brand-container">
  <div class="site-nav-toggle">
    <div class="toggle" aria-label="切换导航栏" role="button">
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
        <span class="toggle-line"></span>
    </div>
  </div>

  <div class="site-meta">

    <a href="/" class="brand" rel="start">
      <i class="logo-line"></i>
      <p class="site-title">CSGrandeur's Thinking</p>
      <i class="logo-line"></i>
    </a>
      <p class="site-subtitle" itemprop="description">Cogito Ergo Sum</p>
  </div>

  <div class="site-nav-right">
    <div class="toggle popup-trigger" aria-label="搜索" role="button">
        <i class="fa fa-search fa-fw fa-lg"></i>
    </div>
  </div>
</div>



<nav class="site-nav">
  <ul class="main-menu menu"><li class="menu-item menu-item-home"><a href="/" rel="section"><i class="fa fa-home fa-fw"></i>首页</a></li><li class="menu-item menu-item-categories"><a href="/categories/" rel="section"><i class="fa fa-th fa-fw"></i>分类</a></li><li class="menu-item menu-item-archives"><a href="/archives/" rel="section"><i class="fa fa-archive fa-fw"></i>归档</a></li>
      <li class="menu-item menu-item-search">
        <a role="button" class="popup-trigger"><i class="fa fa-search fa-fw"></i>搜索
        </a>
      </li>
  </ul>
</nav>



  <div class="search-pop-overlay">
    <div class="popup search-popup">
      <div class="search-header">
        <span class="search-icon">
          <i class="fa fa-search"></i>
        </span>
        <div class="search-input-container">
          <input autocomplete="off" autocapitalize="off" maxlength="80"
                placeholder="搜索..." spellcheck="false"
                type="search" class="search-input">
        </div>
        <span class="popup-btn-close" role="button">
          <i class="fa fa-times-circle"></i>
        </span>
      </div>
      <div class="search-result-container">
        <div class="search-result-icon">
          <i class="fa fa-spinner fa-pulse fa-5x"></i>
        </div>
      </div>
    </div>
  </div>

</header>
        
  
  <aside class="sidebar">

    <div class="sidebar-inner sidebar-nav-active sidebar-toc-active">
      <ul class="sidebar-nav">
        <li class="sidebar-nav-toc">
          文章目录
        </li>
        <li class="sidebar-nav-overview">
          站点概览
        </li>
      </ul>

      <div class="sidebar-panel-container">
        <!--noindex-->
        <div class="post-toc-wrap sidebar-panel">
            <div class="post-toc animated"><ol class="nav"><li class="nav-item nav-level-1"><a class="nav-link" href="#%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95"><span class="nav-number">1.</span> <span class="nav-text">字符串算法</span></a><ol class="nav-child"><li class="nav-item nav-level-2"><a class="nav-link" href="#kmp"><span class="nav-number">1.1.</span> <span class="nav-text">KMP</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E6%9C%80%E7%9F%AD%E5%BE%AA%E7%8E%AF%E8%8A%82"><span class="nav-number">1.1.1.</span> <span class="nav-text">例：最短循环节</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#ac%E8%87%AA%E5%8A%A8%E6%9C%BA"><span class="nav-number">1.2.</span> <span class="nav-text">AC自动机</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E5%87%BA%E7%8E%B0%E6%9C%80%E5%A4%9A%E7%9A%84%E6%A8%A1%E5%BC%8F%E4%B8%B2"><span class="nav-number">1.2.1.</span> <span class="nav-text">例：出现最多的模式串</span></a></li></ol></li><li class="nav-item nav-level-2"><a class="nav-link" href="#%E6%9C%80%E5%B0%8F%E8%A1%A8%E7%A4%BA%E6%B3%95"><span class="nav-number">1.3.</span> <span class="nav-text">最小表示法</span></a><ol class="nav-child"><li class="nav-item nav-level-3"><a class="nav-link" href="#%E4%BE%8B%E5%88%A4%E6%96%AD%E4%B8%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E6%98%AF%E5%90%A6%E5%BE%AA%E7%8E%AF%E5%90%8C%E6%9E%84"><span class="nav-number">1.3.1.</span> <span class="nav-text">例：判断两字符串是否循环同构</span></a></li></ol></li></ol></li></ol></div>
        </div>
        <!--/noindex-->

        <div class="site-overview-wrap sidebar-panel">
          <div class="site-author animated" itemprop="author" itemscope itemtype="http://schema.org/Person">
  <p class="site-author-name" itemprop="name">CSGrandeur</p>
  <div class="site-description" itemprop="description"></div>
</div>
<div class="site-state-wrap animated">
  <nav class="site-state">
      <div class="site-state-item site-state-posts">
        <a href="/archives/">
          <span class="site-state-item-count">72</span>
          <span class="site-state-item-name">日志</span>
        </a>
      </div>
      <div class="site-state-item site-state-categories">
          <a href="/categories/">
        <span class="site-state-item-count">6</span>
        <span class="site-state-item-name">分类</span></a>
      </div>
      <div class="site-state-item site-state-tags">
          <a href="/tags/">
        <span class="site-state-item-count">22</span>
        <span class="site-state-item-name">标签</span></a>
      </div>
  </nav>
</div>

        </div>
      </div>
    </div>

    
  </aside>


    </div>

    <div class="main-inner post posts-expand">


  


<div class="post-block">
  
  

  <article itemscope itemtype="http://schema.org/Article" class="post-content" lang="zh-CN">
    <link itemprop="mainEntityOfPage" href="http://blog.csgrandeur.cn/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/">

    <span hidden itemprop="author" itemscope itemtype="http://schema.org/Person">
      <meta itemprop="image" content="/images/avatar.gif">
      <meta itemprop="name" content="CSGrandeur">
    </span>

    <span hidden itemprop="publisher" itemscope itemtype="http://schema.org/Organization">
      <meta itemprop="name" content="CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>

    <span hidden itemprop="post" itemscope itemtype="http://schema.org/CreativeWork">
      <meta itemprop="name" content="34.字符串算法 | CSGrandeur's Thinking">
      <meta itemprop="description" content="">
    </span>
      <header class="post-header">
        <h1 class="post-title" itemprop="name headline">
          34.字符串算法
        </h1>

        <div class="post-meta-container">
          <div class="post-meta">
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar"></i>
      </span>
      <span class="post-meta-item-text">发表于</span>

      <time title="创建时间：2025-06-04 15:59:11" itemprop="dateCreated datePublished" datetime="2025-06-04T15:59:11+08:00">2025-06-04</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-calendar-check"></i>
      </span>
      <span class="post-meta-item-text">更新于</span>
      <time title="修改时间：2025-06-12 17:25:17" itemprop="dateModified" datetime="2025-06-12T17:25:17+08:00">2025-06-12</time>
    </span>
    <span class="post-meta-item">
      <span class="post-meta-item-icon">
        <i class="far fa-folder"></i>
      </span>
      <span class="post-meta-item-text">分类于</span>
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/ACM/" itemprop="url" rel="index"><span itemprop="name">ACM</span></a>
        </span>
          ，
        <span itemprop="about" itemscope itemtype="http://schema.org/Thing">
          <a href="/categories/ACM/ACMCOURSE/" itemprop="url" rel="index"><span itemprop="name">ACMCOURSE</span></a>
        </span>
    </span>

  
</div>

        </div>
      </header>

    
    
    
    <div class="post-body" itemprop="articleBody"><h1 id="字符串算法">字符串算法</h1>
<p>KMP、AC自动机、字符串哈希、最小表示法。</p>
<span id="more"></span>
<h2 id="kmp">KMP</h2>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">mStr = <span class="string">&quot;aaaaabbcaaab&quot;</span></span><br><span class="line">tStr = <span class="string">&quot;aaab&quot;</span></span><br></pre></td></tr></table></figure>
<p>如何找到 <code>tStr</code> 在 <code>mStr</code>
中出现的位置？如何找出出现的次数？复杂度是多少？</p>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E6%9A%B4%E5%8A%9B.svg" class="">
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">Index1</span><span class="params">(<span class="type">char</span> mStr[], <span class="type">char</span> tStr[])</span> </span>&#123;</span><br><span class="line">  <span class="type">int</span> i, j;</span><br><span class="line">  <span class="comment">// 遍历主字符串的每个位置作为可能的起始位置</span></span><br><span class="line">  <span class="keyword">for</span>(i = <span class="number">0</span>; mStr[i]; i ++) &#123;</span><br><span class="line">    <span class="comment">// 从当前位置i开始，逐个字符比较mStr和tStr</span></span><br><span class="line">    <span class="comment">// 当tStr[j]为&#x27;\0&#x27;（字符串结束）或字符不匹配时退出循环</span></span><br><span class="line">    <span class="keyword">for</span>(j = <span class="number">0</span>; tStr[j] &amp;&amp; mStr[i + j] == tStr[j]; j ++);    <span class="comment">// 这里有分号</span></span><br><span class="line">    </span><br><span class="line">    <span class="comment">// 如果tStr[j]为&#x27;\0&#x27;，说明tStr已经完全匹配</span></span><br><span class="line">    <span class="keyword">if</span>(!tStr[j]) &#123;</span><br><span class="line">        <span class="keyword">return</span> i;  <span class="comment">// 返回匹配的起始位置</span></span><br><span class="line">    &#125;</span><br><span class="line">  &#125;</span><br><span class="line">  <span class="keyword">return</span> <span class="number">-1</span>;  <span class="comment">// 未找到匹配，返回-1</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E6%80%9D%E8%80%83%E6%9A%B4%E5%8A%9B%E6%94%B9%E8%BF%9B.svg" class="">
<p>暴力匹配算法的时间复杂度为 <span class="math inline">\(O(m \times
n)\)</span>，其中 <span class="math inline">\(m\)</span>
是主串长度，<span class="math inline">\(n\)</span>
是模式串长度。要改进这个算法，需要思考两个方向：</p>
<ol type="1">
<li>比较操作的优化
<ul>
<li>字符串比较必须逐个字符进行，这是无法避免的</li>
<li>因此，优化的重点不在于减少单次比较的复杂度</li>
</ul></li>
<li>比较次数的优化
<ul>
<li>暴力匹配中，每次失配后都从主串的下一个位置重新开始比较</li>
<li>这导致了很多不必要的比较操作</li>
<li>例如：当模式串为"aaab"时，如果前三个'a'都匹配，最后一个'b'失配，下一次比较时，我们其实已经知道前两个'a'是匹配的</li>
</ul></li>
</ol>
<p>利用已知信息</p>
<p>在暴力匹配中，每次失配后我们都从主串的下一个位置重新开始比较，这导致了很多重复的比较操作。例如，当模式串为"aaab"时，如果前3个'a'都匹配，最后一个'b'失配，右挪
1 位进行下一次比较时，我们其实已经知道有 2 个'a'是匹配的。</p>
<p>关键问题在于：如何利用已经比较过的信息？当发生失配时，我们是否可以从之前的匹配结果中获取有用信息？能否避免重复比较已经确定匹配的部分？</p>
<p>这些思考最终引出了KMP算法的核心思想：通过预处理模式串，构建 <span
class="math inline">\(next\)</span>
数组，在失配时利用已知信息快速移动模式串，从而减少比较次数。KMP算法的精髓就在于，它能够从失败的匹配中学习，利用已经匹配的信息来指导下一次匹配的位置。</p>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E5%9F%BA%E6%9C%AC%E6%80%9D%E6%83%B3.svg" class="">
<p>核心思想：找到已经匹配的前缀串的最长相等前后缀，把它挪到这个后缀开头的位置进行匹配</p>
<p>如上图，成功匹配的前缀串是 <code>abcab</code>，它的最长相等前后缀是
<code>ab</code>，那么下一次比较就直接让它开头的 <code>ab</code>
对齐到后面的 <code>ab</code> 位置去比对。</p>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_next%E6%95%B0%E7%BB%84.svg" class="">
<p>next数组含义： <code>next[i] = j</code>，
表示当从<code>0</code>开始匹配到 <code>i</code> 位置失败时，让
<code>j</code> 挪到 <code>i</code>
当前所对齐的主串位置继续尝试匹配。</p>
<p>计算 next 参考代码， <code>ts</code> 是模式串</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> nex[<span class="number">1000</span>];</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">BuildNext</span><span class="params">(<span class="type">char</span> ts[])</span> </span>&#123;</span><br><span class="line">    nex[<span class="number">0</span>] = <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>, j = <span class="number">-1</span>; ts[i];) &#123;</span><br><span class="line">        <span class="keyword">if</span>(j == <span class="number">-1</span> || ts[i] == ts[j])</span><br><span class="line">            nex[++i] = ++j;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            j = nex[j];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_next%E8%AE%A1%E7%AE%97%E5%8A%A8%E6%80%81%E6%BC%94%E7%A4%BA.gif" class="">
<p>基于 next 进行匹配，即在 <code>ms</code> 里找 <code>ts</code>
出现的位置</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">KmpMatch</span><span class="params">(<span class="type">char</span> ms[], <span class="type">char</span> ts[])</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> tlen = <span class="built_in">strlen</span>(ts);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>, j = <span class="number">0</span>; ms[i];) &#123;</span><br><span class="line">        <span class="keyword">if</span>(j == <span class="number">-1</span> || ms[i] == ts[j]) &#123;</span><br><span class="line">            <span class="keyword">if</span>(j == tlen - <span class="number">1</span>) &#123;</span><br><span class="line">                <span class="comment">// 确认一次完整匹配，此处可支持各类操作</span></span><br><span class="line">                <span class="comment">// 记录位置、统计次数 返回第一次匹配位置等。</span></span><br><span class="line">                <span class="keyword">return</span> i - tlen + <span class="number">1</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="keyword">else</span> i ++, j ++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> j = nex[j];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/kmp_%E5%8C%B9%E9%85%8D%E6%BC%94%E7%A4%BA.gif" class="">
<h3 id="例最短循环节">例：最短循环节</h3>
<p>给出 <span class="math inline">\(s_{1}\)</span>，猜一个最短的 <span
class="math inline">\(s_{2}\)</span>，使 <span
class="math inline">\(s_{2}\)</span> 能以至少重复 <span
class="math inline">\(2\)</span> 次地重复连接得到 <span
class="math inline">\(s_{1}\)</span>，求 <span
class="math inline">\(s_{2}\)</span> 最短长度。</p>
<p>分析：KMP 的 next
能够标记任意前缀的"最长相等前后缀"，如果字符串是循环构成的，那么这个最长相等前后缀的前缀就会覆盖到最后一次循环前，总长度减去这个前缀长度，就是最短的循环节。<a
href="/2021-04-27-try-to-prove-loop-by-kmp/">点击查看详细的（尝试）证明</a></p>
<p>参考代码</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;string&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;unordered_map&gt;</span></span></span><br><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> std;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxs = <span class="number">1e6</span> + <span class="number">10</span>;</span><br><span class="line"><span class="type">int</span> n;</span><br><span class="line"><span class="type">char</span> ts[maxs];</span><br><span class="line"><span class="type">int</span> nex[maxs];</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">BuildNex</span><span class="params">(<span class="type">char</span> ts[], <span class="type">int</span> nex[])</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    nex[<span class="number">0</span>] = <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>, j = <span class="number">-1</span>; ts[i]; ) &#123;</span><br><span class="line">        <span class="keyword">if</span>(j == <span class="number">-1</span> || ts[i] == ts[j])</span><br><span class="line">            nex[++i] = ++j;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            j = nex[j];</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> len;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d%s&quot;</span>, &amp;len, ts) != EOF) &#123;</span><br><span class="line">        <span class="built_in">BuildNex</span>(ts, nex);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, len - nex[len]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="ac自动机">AC自动机</h2>
<p><a href="/2025-03-12-10-哈希与字典树">回顾
Trie</a>：构建字符范围（比如26个字母）的多叉树，将字符串像查字典一样插入多叉树，查询也是一样，可以作为字符串的哈希方案。</p>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/ac%E8%87%AA%E5%8A%A8%E6%9C%BA_trie.svg" class="">
<ol type="1">
<li>给n个单词，和1个长单词，求有多少个单词是这个长单词的前缀 —— 用 n
个单词建字典树，节点统计单词个数，长单词去匹配，路径上个数求和</li>
<li>给n个单词，和1个短单词，求这个短单词是多少个单词的前缀 —— 用 n
个单词建字典树，节点统计单词个数，短单词匹配成功的节点个数为答案</li>
<li>给两种语言单词对照表，输入任意单词，输出对照另一个语言的单词</li>
</ol>
<p>KMP：找 <span class="math inline">\(1\)</span> 个模式串在 <span
class="math inline">\(1\)</span> 个文本中出现的位置</p>
<p>思考： <span class="math inline">\(n\)</span> 个模式串在 <span
class="math inline">\(1\)</span> 个文本中出现的位置，怎么办？建 <span
class="math inline">\(n\)</span> 个 next
数组然后遍历搞？让模式串每个后缀（即从不同位置开始）在字典树上匹配一遍？都太慢了。</p>
<ol type="1">
<li>将 <span class="math inline">\(n\)</span> 个模式串放入Trie</li>
<li>在 Trie
上构建"next数组"——真谛是失配指针——在Trie上匹配失败时，也可以记录一个"下次从哪里开始匹配"</li>
</ol>
<p>这就是AC自动机的基本思想。</p>
<p>每个节点<span class="math inline">\(A\)</span>的 <code>fail</code>
指针指向另一个节点<span class="math inline">\(B\)</span>，<span
class="math inline">\(B\)</span>节点代表的前缀是<span
class="math inline">\(A\)</span>节点前缀的最长后缀。比如从跟节点来到
<span class="math inline">\(A\)</span> 节点是
<code>"abcde"</code>，其中<span class="math inline">\(A\)</span>
节点存的是 <code>'e'</code>，<span class="math inline">\(A\)</span>
的适配指针指向另一个保存 <code>'e'</code> 的节点<span
class="math inline">\(B\)</span>，从根节点到<span
class="math inline">\(B\)</span>的路径可能就会是 <code>"bcde"</code>
或者 <code>"cde"</code> ，具体如何要看模式串集合是否包含有
<code>"bcde"</code> 或 <code>"cde"</code> 这样的前缀的字符串。</p>
<p>构建过程：</p>
<ol type="1">
<li>根节点的子节点的 <code>fail</code> 指向根</li>
<li>BFS 遍历每个节点，为其所有子节点设置 <code>fail</code> 指针
<ul>
<li>若父节点的 <code>fail</code> 有相同字符的子节点，则指向该子节点</li>
<li>否则递归跳转父节点的 <code>fail</code>，直到找到或回到根</li>
</ul></li>
</ol>
<p>匹配过程：</p>
<ol type="1">
<li>从根节点开始，按文本字符转移</li>
<li>每次转移后，检查当前节点及其 fail 链上的节点是否为模式串结尾</li>
<li>统计所有匹配的模式串</li>
</ol>
<p>复杂度：</p>
<ul>
<li>构建：<span class="math inline">\(O (所有模式串长度之和 + 字符集大小
\times 节点数)\)</span></li>
<li>匹配：<span class="math inline">\(O (文本长度 +
匹配数)\)</span></li>
</ul>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/ac%E8%87%AA%E5%8A%A8%E6%9C%BA.svg" class="">
<h3 id="例出现最多的模式串">例：出现最多的模式串</h3>
<p>给一系列模式串，和一个长文本，求长文本中出现最多的模式串。</p>
<p>方案：构建AC自动机，对每一次匹配到的位置，都沿着失配指针遍历一遍直到根，路径上所有完整单词都计入匹配。最后根据统计结果输出。</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br><span class="line">66</span><br><span class="line">67</span><br><span class="line">68</span><br><span class="line">69</span><br><span class="line">70</span><br><span class="line">71</span><br><span class="line">72</span><br><span class="line">73</span><br><span class="line">74</span><br><span class="line">75</span><br><span class="line">76</span><br><span class="line">77</span><br><span class="line">78</span><br><span class="line">79</span><br><span class="line">80</span><br><span class="line">81</span><br><span class="line">82</span><br><span class="line">83</span><br><span class="line">84</span><br><span class="line">85</span><br><span class="line">86</span><br><span class="line">87</span><br><span class="line">88</span><br><span class="line">89</span><br><span class="line">90</span><br><span class="line">91</span><br><span class="line">92</span><br><span class="line">93</span><br><span class="line">94</span><br><span class="line">95</span><br><span class="line">96</span><br><span class="line">97</span><br><span class="line">98</span><br><span class="line">99</span><br><span class="line">100</span><br><span class="line">101</span><br><span class="line">102</span><br><span class="line">103</span><br><span class="line">104</span><br><span class="line">105</span><br><span class="line">106</span><br><span class="line">107</span><br><span class="line">108</span><br><span class="line">109</span><br><span class="line">110</span><br><span class="line">111</span><br><span class="line">112</span><br><span class="line">113</span><br><span class="line">114</span><br><span class="line">115</span><br><span class="line">116</span><br><span class="line">117</span><br><span class="line">118</span><br><span class="line">119</span><br><span class="line">120</span><br><span class="line">121</span><br><span class="line">122</span><br><span class="line">123</span><br><span class="line">124</span><br><span class="line">125</span><br><span class="line">126</span><br><span class="line">127</span><br><span class="line">128</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstdio&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;cstring&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;algorithm&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;vector&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;queue&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span><span class="string">&lt;functional&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> std::pair&lt;<span class="type">int</span>, <span class="type">int</span>&gt; pii;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxn = <span class="number">1e5</span>;</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> maxm = <span class="number">1e6</span> + <span class="number">10</span>;</span><br><span class="line"><span class="keyword">struct</span> <span class="title class_">Trie</span> &#123;</span><br><span class="line">    <span class="type">int</span> ch[<span class="number">26</span>];</span><br><span class="line">    <span class="type">int</span> fail;</span><br><span class="line">    <span class="type">int</span> end;</span><br><span class="line">&#125;;</span><br><span class="line">Trie tr[maxn];</span><br><span class="line"><span class="type">int</span> n, tp;</span><br><span class="line"><span class="type">char</span> st[<span class="number">211</span>][<span class="number">111</span>];</span><br><span class="line"><span class="type">char</span> buf[maxm];</span><br><span class="line"><span class="type">const</span> <span class="type">int</span> ROOT = <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">Insert</span><span class="params">(<span class="type">char</span> s[], <span class="type">int</span> idx)</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> p = ROOT;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; s[i]; i ++) &#123;</span><br><span class="line">        <span class="type">int</span> c = s[i] - <span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">        <span class="keyword">if</span>(tr[p].ch[c] == <span class="number">-1</span>) &#123;</span><br><span class="line">            tr[p].ch[c] = tp ++;</span><br><span class="line">        &#125;</span><br><span class="line">        p = tr[p].ch[c];</span><br><span class="line">    &#125;</span><br><span class="line">    tr[p].end = idx;        <span class="comment">// 记录这是第 idx 个字符串的结束点</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">BuildFail</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    std::queue&lt;<span class="type">int</span>&gt; q;</span><br><span class="line">    <span class="comment">// 根节点的子节点fail指向根</span></span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">26</span>; i ++) &#123;</span><br><span class="line">        <span class="keyword">if</span>(tr[ROOT].ch[i] != <span class="number">-1</span>) &#123;</span><br><span class="line">            tr[tr[ROOT].ch[i]].fail = <span class="number">0</span>;</span><br><span class="line">            q.<span class="built_in">push</span>(tr[ROOT].ch[i]);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    </span><br><span class="line">    <span class="comment">// BFS遍历每个节点,为其子节点设置fail指针</span></span><br><span class="line">    <span class="keyword">while</span>(!q.<span class="built_in">empty</span>()) &#123;</span><br><span class="line">        <span class="type">int</span> u = q.<span class="built_in">front</span>();</span><br><span class="line">        q.<span class="built_in">pop</span>();</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 遍历所有可能的子节点</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="number">26</span>; i ++) &#123;</span><br><span class="line">            <span class="keyword">if</span>(tr[u].ch[i] != <span class="number">-1</span>) &#123;</span><br><span class="line">                <span class="type">int</span> v = tr[u].ch[i];    <span class="comment">// 当前节点的子节点</span></span><br><span class="line">                <span class="type">int</span> f = tr[u].fail;     <span class="comment">// 当前节点的fail节点</span></span><br><span class="line">                </span><br><span class="line">                <span class="comment">// 沿着fail指针找到对应字符的转移</span></span><br><span class="line">                <span class="keyword">while</span>(f != ROOT &amp;&amp; tr[f].ch[i] == <span class="number">-1</span>) &#123;</span><br><span class="line">                    f = tr[f].fail;</span><br><span class="line">                &#125;</span><br><span class="line">                </span><br><span class="line">                <span class="comment">// 找到转移或到达根节点</span></span><br><span class="line">                <span class="keyword">if</span>(tr[f].ch[i] != <span class="number">-1</span>) &#123;</span><br><span class="line">                    tr[v].fail = tr[f].ch[i];</span><br><span class="line">                &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                    tr[v].fail = ROOT;</span><br><span class="line">                &#125;</span><br><span class="line">                </span><br><span class="line">                q.<span class="built_in">push</span>(v);</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">// 在文本串中查找所有模式串的出现次数</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">FindMaxPatterns</span><span class="params">(<span class="type">char</span> text[])</span> </span>&#123;</span><br><span class="line">    <span class="type">int</span> len = <span class="built_in">strlen</span>(text);</span><br><span class="line">    <span class="function">std::vector&lt;pii&gt; <span class="title">cnt</span><span class="params">(n, &#123;<span class="number">0</span>, <span class="number">0</span>&#125;)</span></span>;  <span class="comment">// 记录每个模式串出现次数</span></span><br><span class="line">    </span><br><span class="line">    <span class="comment">// 从根节点开始匹配</span></span><br><span class="line">    <span class="type">int</span> p = ROOT;</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; len; i++) &#123;</span><br><span class="line">        <span class="type">int</span> c = text[i] - <span class="string">&#x27;a&#x27;</span>;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 沿着fail指针找到可以转移的位置</span></span><br><span class="line">        <span class="keyword">while</span>(p != ROOT &amp;&amp; tr[p].ch[c] == <span class="number">-1</span>) &#123;</span><br><span class="line">            p = tr[p].fail; </span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 找到转移或到达根节点</span></span><br><span class="line">        <span class="keyword">if</span>(tr[p].ch[c] != <span class="number">-1</span>) &#123;</span><br><span class="line">            p = tr[p].ch[c];</span><br><span class="line">        &#125;</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 统计当前位置及fail链上所有模式串</span></span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> t = p; t != ROOT; t = tr[t].fail) &#123;</span><br><span class="line">            <span class="keyword">if</span>(tr[t].end != <span class="number">-1</span>) &#123;</span><br><span class="line">                cnt[tr[t].end].first ++;    <span class="comment">// 统计匹配成功次数</span></span><br><span class="line">                cnt[tr[t].end].second = tr[t].end;  <span class="comment">// 模式串序号</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">// 找出最大出现次数</span></span><br><span class="line">    std::<span class="built_in">sort</span>(cnt.<span class="built_in">begin</span>(), cnt.<span class="built_in">end</span>(), [](<span class="type">const</span> pii &amp;a, <span class="type">const</span> pii &amp;b) &#123;</span><br><span class="line">        <span class="keyword">return</span> a.first &gt; b.first || (a.first == b.first &amp;&amp; a.second &lt; b.second);</span><br><span class="line">    &#125;);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%d\n&quot;</span>, cnt[<span class="number">0</span>].first);</span><br><span class="line">    <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; cnt[i].first == cnt[<span class="number">0</span>].first; i ++) &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%s\n&quot;</span>, st[cnt[i].second]);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">while</span>(<span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>, &amp;n) != EOF &amp;&amp; n) &#123;</span><br><span class="line">        tp = <span class="number">1</span>;</span><br><span class="line">        <span class="built_in">memset</span>(tr, <span class="number">-1</span>, <span class="built_in">sizeof</span>(tr));</span><br><span class="line">        <span class="keyword">for</span>(<span class="type">int</span> i = <span class="number">0</span>; i &lt; n; i ++) &#123;</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, st[i]);</span><br><span class="line">            <span class="built_in">Insert</span>(st[i], i);    <span class="comment">// 插入字典树</span></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="built_in">BuildFail</span>();        <span class="comment">// 构建失配指针</span></span><br><span class="line">        </span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, buf);</span><br><span class="line">        </span><br><span class="line">        <span class="comment">// 查找模式串</span></span><br><span class="line">        <span class="built_in">FindMaxPatterns</span>(buf);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="最小表示法">最小表示法</h2>
<p>当字符串 <span class="math inline">\(S\)</span> 中可以选定一个位置
<span class="math inline">\(i\)</span> 满足</p>
<p><span class="math display">\[S[i\cdots n]+S[1\cdots
i-1]=T\]</span></p>
<p>则称 <span class="math inline">\(S\)</span> 与 <span
class="math inline">\(T\)</span> <strong>循环同构</strong></p>
<p>例如 <code>abcdefg</code> 与 <code>efgabcd</code>
是循环同构的，循环左移或循环右移能得到另一个字符串。</p>
<p><strong>最小表示即字符串 <span class="math inline">\(S\)</span>
循环同构的所有字符串中字典序最小的字符串</strong>。</p>
<h3 id="例判断两字符串是否循环同构">例：判断两字符串是否循环同构</h3>
<p>个两个字符串 <span class="math inline">\(s_{1}\)</span> 和 <span
class="math inline">\(s_{2}\)</span> 判断是否循环同构，字符串长度为
<span class="math inline">\(n\)</span></p>
<p>基本暴力：枚举 <span class="math inline">\(s_{2}\)</span>
的所有循环起点与 <span class="math inline">\(s_{1}\)</span> 比较，<span
class="math inline">\(O(n^2)\)</span></p>
<p>改进思路：两个 <span class="math inline">\(s_{1}\)</span>
拼接形成一个二倍长度的字符串 <span
class="math inline">\(u=s_{1}+s_{1}\)</span>，让 <span
class="math inline">\(s_{2}\)</span> 在 <span
class="math inline">\(u\)</span> 上做 KMP，<span
class="math inline">\(O(n)\)</span>，但对于这个题来说， KMP
有点杀鸡用牛刀。</p>
<p>最小表示思路：比较两个字符串的最小表示的串是否相等。</p>
<p>一个字符串的最小表示计算方法：</p>
<ol type="1">
<li>初始化 <code>i=0, j=1</code>，考察 <code>i</code> 开始的循环串和
<code>j</code> 开始的循环串的匹配长度 <code>k</code></li>
<li>当 <code>s[i + k] &gt; s[j + k]</code>，可将 <code>i</code> 跳到
<code>i + k + 1</code> 进行下一轮比较</li>
<li>直到遍历结束，输出 <code>i</code> 与 <code>j</code> 较小的那个</li>
</ol>
<p>分析第 2 步可以跳到 <code>i + k + 1</code>
的原因：最小表示是要找字典序最小的循环串，<code>i</code> 跳到
<code>i + (p = 1 ~ k)</code> 的位置没有必要，因为至少有
<code>j + (p = 1 ~ k)</code> 的循环串的字典序比它小，即
<code>j+p ~ j+k-1</code> 与 <code>i+p ~ i+k-1</code>
一一对应相等，而<code>s[i + k] &gt; s[j + k]</code>，从而 <code>i</code>
跳到 <code>i + (p&lt;=k)</code> 的位置一定得不到字典序最小的循环串。</p>
<img src="/2025-06-04-34-%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%AE%97%E6%B3%95/%E6%9C%80%E5%B0%8F%E8%A1%A8%E7%A4%BA_ijn.svg" class="">
<p>参考代码</p>
<figure class="highlight cpp"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> k = <span class="number">0</span>, i = <span class="number">0</span>, j = <span class="number">1</span>;</span><br><span class="line"><span class="keyword">while</span> (k &lt; n &amp;&amp; i &lt; n &amp;&amp; j &lt; n) &#123;</span><br><span class="line">    <span class="keyword">if</span> (s[(i + k) % n] == s[(j + k) % n]) &#123;</span><br><span class="line">            k++;</span><br><span class="line">    &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">if</span>(s[(i + k) % n] &gt; s[(j + k) % n]) &#123;</span><br><span class="line">            i = i + k + <span class="number">1</span>;</span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            j = j + k + <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (i == j) i++;    <span class="comment">// i 和 j 不能重叠</span></span><br><span class="line">        k = <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line">i = <span class="built_in">min</span>(i, j);              <span class="comment">// 得到最小循环串的起始位置，即最小表示</span></span><br></pre></td></tr></table></figure>

    </div>

    
    
    

    <footer class="post-footer">
          <div class="post-tags">
              <a href="/tags/ACM/" rel="tag"># ACM</a>
              <a href="/tags/Algorithm/" rel="tag"># Algorithm</a>
          </div>

        

          <div class="post-nav">
            <div class="post-nav-item">
                <a href="/2025-05-23-33-%E8%8C%83%E5%9B%B4%E7%BB%9F%E8%AE%A1/" rel="prev" title="33.范围统计">
                  <i class="fa fa-angle-left"></i> 33.范围统计
                </a>
            </div>
            <div class="post-nav-item">
                <a href="/2025-06-11-35-%E6%95%B0%E8%AE%BA%E5%85%A5%E9%97%A8/" rel="next" title="35.数论入门">
                  35.数论入门 <i class="fa fa-angle-right"></i>
                </a>
            </div>
          </div>
    </footer>
  </article>
</div>






    <div class="comments utterances-container"></div>
</div>
  </main>

  <footer class="footer">
    <div class="footer-inner">

  <div class="copyright">
    &copy; 
    <span itemprop="copyrightYear">2025</span>
    <span class="with-love">
      <i class="fa fa-heart"></i>
    </span>
    <span class="author" itemprop="copyrightHolder">CSGrandeur</span>
  </div>
  <div class="powered-by">由 <a href="https://hexo.io/" rel="noopener" target="_blank">Hexo</a> & <a href="https://theme-next.js.org/" rel="noopener" target="_blank">NexT.Gemini</a> 强力驱动
  </div>

    </div>
  </footer>

  
  <div class="toggle sidebar-toggle" role="button">
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
    <span class="toggle-line"></span>
  </div>
  <div class="sidebar-dimmer"></div>
  <div class="back-to-top" role="button" aria-label="返回顶部">
    <i class="fa fa-arrow-up fa-lg"></i>
    <span>0%</span>
  </div>

<noscript>
  <div class="noscript-warning">Theme NexT works best with JavaScript enabled</div>
</noscript>


  
  <script src="https://fastly.jsdelivr.net/npm/animejs@3.2.1/lib/anime.min.js" integrity="sha256-XL2inqUJaslATFnHdJOi9GfQ60on8Wx1C2H8DYiN1xY=" crossorigin="anonymous"></script>
  <script src="https://fastly.jsdelivr.net/npm/@next-theme/pjax@0.6.0/pjax.min.js" integrity="sha256-vxLn1tSKWD4dqbMRyv940UYw4sXgMtYcK6reefzZrao=" crossorigin="anonymous"></script>
<script src="/js/comments.js"></script><script src="/js/utils.js"></script><script src="/js/motion.js"></script><script src="/js/sidebar.js"></script><script src="/js/next-boot.js"></script><script src="/js/pjax.js"></script>

  <script src="https://fastly.jsdelivr.net/npm/hexo-generator-searchdb@1.4.1/dist/search.js" integrity="sha256-1kfA5uHPf65M5cphT2dvymhkuyHPQp5A53EGZOnOLmc=" crossorigin="anonymous"></script>
<script src="/js/third-party/search/local-search.js"></script>







  




  

  <script class="next-config" data-name="enableMath" type="application/json">true</script><script class="next-config" data-name="mathjax" type="application/json">{"enable":true,"tags":"none","js":{"url":"https://fastly.jsdelivr.net/npm/mathjax@3.2.2/es5/tex-mml-chtml.js","integrity":"sha256-MASABpB4tYktI2Oitl4t+78w/lyA+D7b/s9GEP0JOGI="}}</script>
<script src="/js/third-party/math/mathjax.js"></script>


<script class="next-config" data-name="utterances" type="application/json">{"enable":true,"repo":"CSGrandeur/csgrandeur.github.io","issue_term":"pathname","theme":"github-light"}</script>
<script src="/js/third-party/comments/utterances.js"></script>

</body>
</html>
